import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;


public class SkipList
{
	private int listLevel = 0;
	private ArrayList<ArrayList<SkipListNode>> allLists;
	
	public SkipList()
	{	
		allLists = new ArrayList<ArrayList<SkipListNode>>();
		
		// Die erste Ebene der Liste von allen Listen hinzufügen.
		this.allLists.add(new ArrayList<SkipListNode>());
		this.listLevel += 1;
	}
	
	
	public void insert(int value)
	{
		// Wenn Wert vorhanden muss nichts gemacht werden.
		if (allLists.get(0).contains(new SkipListNode(value, null, null)))
			return;
		
		// Den Wert aufjedenfall in die erste Ebene einfügen.
		SkipListNode newNode = new SkipListNode(value, null, null);
		this.allLists.get(0).add(newNode);
		Collections.sort(this.allLists.get(0));
		
		// Funktion zum Einfügen in höhere Ebenen.
		for(int i = 0; i < listLevel; i++)
		{
			if (allLists.get(i).size() < 2) return;
			if (ListNodeInUpperList(i))
			{
				SkipListNode newNodeInUpperList = new SkipListNode(value
						, allLists.get(i), newNode);
				newNode = newNodeInUpperList;
				
				// Prüfen ob höhere Ebene vorhanden.
				if (this.listLevel <= i + 1)
					// Neue Ebene hinzufügen
					AddNewLevel();
				
				allLists.get(i + 1).add(newNode);
				Collections.sort(allLists.get(i + 1));
				continue;
			}
			break;
		}
		
	}
	
	private void AddNewLevel()
	{
		allLists.add(new ArrayList<SkipListNode>());
		this.listLevel += 1;
	}
	
	private Boolean ListNodeInUpperList(int list)
	{
		Random ran = new Random();
		return ran.nextInt(20) < Math.log(this.allLists.get(list).size()) * Math.E;
	}
	
	public void PrintSkipList()
	{
		for(int i = 0; i < this.listLevel; i++)
		{
			int[] levelValues = new int[this.allLists.get(i).size()];
			for (int t = 0; t < this.allLists.get(i).size(); t++)
				levelValues[t] = this.allLists.get(i).get(t).get_value();
			
			System.out.println(Arrays.toString(levelValues));
		}
	}

}
